#ifndef __TRIE_HPP__
#define __TRIE_HPP__

#include <exception>
#include <utility>
#include <ostream>
#include <string>
#include <vector>
#include <map>
#include <cstdlib>
#include <fstream>

using namespace std;

template <typename TType>
class Trie {
private:
  // Abstract node
  class Node {
  public:
    virtual ~Node() {};
    virtual bool isLeaf() const = 0;
    virtual size_t leafs () const = 0;
    virtual size_t nodes () const = 0;
  };
  
  // Leaf node
  class TNode : public Node {
  private:
    TType v;
  public:
    TNode (const TType& v) : Node(), v(v) 
    {}

    bool isLeaf() const 
    { return true; }

    const TType& value () const
    { return v; }

    TType& value () 
    { return v; }

    size_t leafs () const
    { return 1; }

    size_t nodes () const
    { return 1; }
  };

  // Internal node
  class INode : public Node {
  private:
    Node * children[27];
  public:
    INode ()
    {
      for(size_t i = 0; i < 27; ++i)
	children[i] = NULL;
    }
    
    ~INode () 
    {
      for(size_t i = 0; i < 27; ++i)
	if ( children[i] != NULL )
	  delete children[i];

    }
    
    bool isLeaf() const { return false; }
    
    void insert(const string& key, TType& val) 
    {
      if( key.length() == 0 ) {
	if (children[0] == NULL)
	  children[0] = new TNode(val);
	else
	  ((TNode*)children[0])->value() = val;
	return;
      } else if ( key.length() == 1 ) {
	if ( children[1+key[0]-'a'] == NULL )
	  children[1+key[0]-'a'] = new TNode(val);
	else if ( children[1+key[0]-'a']->isLeaf() )
	  ((TNode*)children[1+key[0]-'a'])->value() = val;
	else
	  ((INode*)children[1+key[0]-'a'])->insert("", val);
	return;
      }

      if ( children[1+key[0]-'a'] == NULL ) {
	children[1+key[0]-'a'] = new INode();
      } else if ( children[1+key[0]-'a']->isLeaf() ) {
	TNode * tnode = (TNode*)children[1+key[0]-'a'];
	children[1+key[0]-'a'] = new INode();
	((INode*)children[1+key[0]-'a'])->children[0] = tnode;
      }

      ((INode*)children[1+key[0]-'a'])->insert(key.substr(1), val);
      return;
    }

    TNode* exact_lookup(const string& key) const
    {
      if ( key.length() == 0 ) 
	return (TNode*)children[0];
      else if ( children[1+key[0]-'a'] == NULL ) 
	return NULL;
      else if ( key.length() == 1 && children[1+key[0]-'a']->isLeaf() ) 
	return (TNode*)children[1+key[0]-'a'];
      else
	return ((INode*)children[1+key[0]-'a'])->exact_lookup(key.substr(1));
    }

    size_t leafs () const
    {
      size_t leafs = 0;
      for(size_t i = 0; i < 27; ++i)
	if ( children[i] != NULL ) leafs += children[i]->leafs();
      return leafs;
    }

    size_t nodes () const
    {
      size_t nodes = 1;
      for(size_t i = 0; i < 27; ++i)
	if ( children[i] != NULL ) nodes += children[i]->nodes();
      return nodes;
    }
  };
  
  INode root;
public:
  void insert(const string& key, TType& val)
  {
    root.insert(key, val);
  }

  pair<bool, TType> exact_lookup(const string&key ) const
  {
    TNode * res = root.exact_lookup(key);
    if ( res == NULL ) return pair<bool,TType>(false, TType());
    else return pair<bool,TType>(true, res->value());
  }

  size_t leafs () const
  { return root.leafs(); }

  size_t nodes () const
  { return root.nodes(); }
};

#endif
